package tree;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author kaho
 * @since 2021/3/1
 */
public class _173_二叉搜索树迭代器 {

    /**
     * 实现一个二叉搜索树迭代器。你将使用二叉搜索树的根节点初始化迭代器。
     *
     * 调用 next() 将返回二叉搜索树中的下一个最小的数。
     */
    class BSTIterator {
        Deque<Integer> queue = new ArrayDeque<>();

        public BSTIterator(TreeNode root) {
            inorderTree(root);
        }

        private void inorderTree(TreeNode root) {
            if (root == null) {
                return;
            }
            inorderTree(root.left);
            queue.add(root.val);
            inorderTree(root.right);
        }

        public int next() {
            return queue.remove();
        }

        public boolean hasNext() {
            return !queue.isEmpty();
        }
    }
}
